home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 15043 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.7 KB  |  99 lines
  1. Path: grimsel.zurich.ibm.com!usenet
  2. From: wgk@zurich.ibm.com (Keith Whittingham)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: Can I do it recursively?
  5. Date: 3 Apr 1996 09:05:26 GMT
  6. Organization: IBM Research, ZRH
  7. Message-ID: <4jtf0m$30s@grimsel.zurich.ibm.com>
  8. References: <4jrcqj$3s1@nuscc.nus.sg>
  9. Reply-To: wgk@zurich.ibm.com
  10. NNTP-Posting-Host: pine.zurich.ibm.com
  11. X-Newsreader: IBM NewsReader/2 v1.00
  12.  
  13. In <4jrcqj$3s1@nuscc.nus.sg>, eng50636@leonis.nus.sg (Sun Jian) writes:
  14. >  I am doing a program of a famous problem(forget the name, sorry). It is 
  15. >about how a horse can travel through the whole 8x8 chess board,without 
  16. >repeating any position that has been travelled(may seem to easy for 
  17. >experts---I am only a beginner). I want to do it by recursion. But it 
  18. >seems quite impossible since the run-time is too long. 
  19.  
  20.  
  21. I have not heard of this problem before but I guess without thinking too
  22. long that recursion should work OK. You need an 8 x 8 array to keep
  23. track of where you've been, and a depth counter to know when you've
  24. visited 64 squares. Stack shouldn't be too much of a problem providing
  25. you keep stack variables to a minimum - there needs to be 64 recursive
  26. calls so it there are 20 bytes of return, address, arguments and auto
  27. variables you still only use 1.2K of stack.
  28.  
  29. Recursion is probably the best way of handling the problem without 
  30. writing a very complex algorithm. The code should look something like
  31. this...
  32.  
  33. char BeenThere[8][8];
  34.  
  35. int IsValid(int Coord)
  36.   {
  37.   return ((Coord >= 0) && (Coord < 8);
  38.   }
  39.  
  40.  
  41. int Visit(int x,int y)
  42.   {
  43.   int Result = 0;
  44.   static int Depth;
  45.  
  46.   if(Isvalid(x) && Isvalid(y))
  47.     {
  48.     if(!BeenThere[x][y])
  49.       {
  50.       BeenThere[x][y] = 1;
  51.       if(++Depth == 8*8)
  52.         {
  53.         Result = 1;
  54.         }
  55.       else
  56.         {
  57.         Result = Visit(x+1, y+2);
  58.         if(!Result) Result = Visit(x+2, y+1);
  59.         if(!Result) Result = Visit(x+2, y-1);
  60.         if(!Result) Result = Visit(x+1, y-2);
  61.         /* etc... */
  62.         }
  63.       if(!Result)
  64.         {
  65.         BeenTher[x][y] = 0;
  66.         Depth--;
  67.         }
  68.       }
  69.     }
  70.  
  71.   return Result;
  72.   }
  73.  
  74. main()
  75.   {
  76.   puts(Visit(0, 0) ? "0,0 is OK" : "0,0 is not OK");
  77.  
  78.   return 0;
  79.   }
  80.  
  81. As you can see the starting position may effect the result? You may want to
  82. loop through all possible positions in the main.
  83.  
  84. The above code can, I'm sure, be beautified but the idea should work I think.
  85.  
  86. If the algorithm is slow then it could be optimised (I think) by checking
  87. for isolated squares at the top of the Visit() function - "If there are
  88. squares that can't be reached then there's no point in carrying on down
  89. this path". This would probably be more suitable to chess boards bigger
  90. than 8 x 8.
  91.  
  92.  
  93. Hope that helps...
  94.  
  95. Keith
  96.  
  97.  
  98.  
  99.